package com.sunny.l60;

import java.util.ArrayList;

/**
 * @Author zsunny
 * @Date 2018/9/14 11:09
 * @Mail zsunny@yeah.net
 */
public class Solution {
    public ArrayList<Integer> grayCode(int n) {
        ArrayList<Integer> dp = new ArrayList<>();
        if(0 == n) {
            dp.add(0);
            return dp;
        }
        dp.add(0);
        dp.add(1);
        int base = 2;
        for(int i=1;i<n;i++){
            ArrayList<Integer> tmp = new ArrayList<>(dp);
            for(int j=dp.size()-1;j>=0;j--){
                tmp.add(dp.get(j)+base);
            }
            dp = tmp;
            base <<= 1;
        }
        return dp;
    }
}
